﻿namespace Gaur
{
    using System;
    using System.Linq;
    using C5;

    /// <summary>
    /// Finite automaton
    /// </summary>
    public class Fa
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="Fa"/> class.
        /// </summary>
        public Fa()
        {
            this.StartState = -1;
            this.AcceptStates = new Set<int>();
            this.States = new HashDictionary<int, IState>();
            this.Trans = new HashDictionary<int, IDictionary<int, Set<char>>>();
        }

        /// <summary>
        /// Gets or sets StartState.
        /// </summary>
        public int StartState { get; set; }

        /// <summary>
        /// Gets or sets AcceptStates.
        /// </summary>
        public Set<int> AcceptStates { get; set; }

        /// <summary>
        /// Gets or sets Trans.
        /// </summary>
        public IDictionary<int, IDictionary<int, Set<char>>> Trans { get; set; }

        /// <summary>
        /// Gets or sets States.
        /// </summary>
        public IDictionary<int, IState> States { get; set; }

        public Fa Clone()
        {
            Fa clone = new Fa();
            clone.StartState = this.StartState;
            clone.AcceptStates = this.AcceptStates.Clone() as Set<int>;
            clone.States = (HashDictionary<int, IState>)this.States.Clone();
            clone.Trans = (IDictionary<int, IDictionary<int, Set<char>>>)this.Trans.Clone();
            return clone;
        }

        /// <summary>
        /// adds state to FA without checking if state with same content already exists
        /// </summary>
        /// <param name="state">
        /// The state.
        /// </param>
        /// <returns>
        /// Identification number of new state
        /// </returns>
        public int NewState(IState state)
        {
            int key;
            if (!this.States.Keys.IsEmpty)
            {
                key = this.States.Keys.Max() + 1;
            }
            else
            {
                key = 1;
            }
            
            this.States.Add(key, state);
            return key;
        }

        public int AddState()
        {
            //if (this.States.IsEmpty)
            //{
            //    States.Add(1);
            //    return 1;
            //}
            //else
            //{
            //    int newState = this.States.Last() + 1;
            //    this.States.Add(newState);
            //    return newState;
            //}
            return 1;
        }

        public void AddTrans(int s1, char lab, int s2)
        {
            // check if States s1 and s2 exist
            if (States.Contains(s1) && States.Contains(s2))
            {
                if (!Trans.Contains(s1)) // no transitions from state s1
                {
                    IDictionary<int, Set<char>> s1Trans = new HashDictionary<int, Set<char>>();
                    s1Trans.Add(s2, new Set<char>(lab));
                    this.Trans.Add(s1, s1Trans);
                }
                else
                {
                    if (Trans[s1].Contains(s2)) // we already have transition from s1 to s2
                    {
                        Trans[s1][s2].Add(lab);
                    }
                    else // no transitions to s2 exist from s1
                    {
                        Trans[s1].Add(s2, new Set<char>(lab));
                    }
                }
            }
            else
            {
                throw(new Exception("State does not exist"));
            }
        }

        // state is live if accept state is reachable from it
        public Set<int> GetLiveStates()
        {
            ArrayList<int> candidates = new ArrayList<int>();
            candidates.AddAll(this.States.Keys);
            candidates.RemoveAll(this.AcceptStates);

            Set<int> liveStates = new Set<int>();
            liveStates.AddAll(this.AcceptStates);

            Set<int> newLiveStates = new Set<int>();

            do 
            {
                newLiveStates.Clear();

                foreach (int candidateState in candidates)
                {
                    if (Trans.Contains(candidateState) && !Trans[candidateState].Keys.IsEmpty)
                    {
                        // if state has transition to live state
                        if (!(liveStates * new Set<int>(Trans[candidateState].Keys)).IsEmpty)
                        {
                            newLiveStates.Add(candidateState);
                        }
                    }
                }

                liveStates.AddAll(newLiveStates);
                candidates.RemoveAll(newLiveStates);
            } while (!newLiveStates.IsEmpty);

            return liveStates;
        }

        // for given state, return all States immediately reachable from it
        public Set<int> Closure(int state)
        {
            Set<int> closure = new Set<int>();

            foreach (int transitionState in Trans[state].Keys)
            {
                 if (!Trans[state][transitionState].IsEmpty)
                     closure.Add(transitionState);
            }

            return closure;
        }

        // closure for set of States
        public Set<int> Closure(Set<int> states)
        {
            Set<int> closure = new Set<int>();

            foreach (int state in states)
            {
                closure.AddAll(this.Closure(state));
            }

            return closure;
        }

        // state is reachable if there is at least one path from start state to it
        public Set<int> GetReachableStates()
        {
            Set<int> reachableStates = new Set<int>();
            reachableStates.Add(this.StartState);

            Set<int> closureDifference = new Set<int>();
            closureDifference.Add(this.StartState);

            do 
            {
                closureDifference = Closure(closureDifference) - reachableStates;
                reachableStates.AddAll(closureDifference);

            } while (!closureDifference.IsEmpty);

            return reachableStates;
        }

        public Set<int> GetStates()
        {
            Set<int> allStates = new Set<int>();
            allStates.AddAll(this.States.Keys);
            return allStates;
        }

        public void RemoveUnreachableStates()
        {
            this.RemoveStates(GetStates() - GetReachableStates());
        }

        // removes all dead States from automaton, along with their transitions. State is dead if it is not alive
        // i.e. if none of accepting States is reachable from it.
        public void RemoveDeadStates()
        {
            this.RemoveStates(GetStates() - GetLiveStates());
        }

        // remove States and all transitions starting or ending in removed States
        public void RemoveStates(Set<int> removableStates)
        {
            if (States.Contains(this.StartState))
            {
                this.StartState = -1;
            }

            foreach (int r in removableStates)
            {
                this.States.Remove(r);
                if (this.Trans.Contains(r))
                {
                    this.Trans.Remove(r);
                }
            }

            foreach (int state in this.States.Keys)
            {
                foreach (int r in removableStates)
                {
                    if (this.Trans.Contains(state))
                    {
                        this.Trans[state].Remove(r);
                    }
                }
            }
        }

        public void Simplify()
        {
            /*
             * Finite automaton is "Simplified", iff
             * 1. it contains one state, no accepting States and no transitions from that single state
             * 2. all States are useful. State is useful if it is reachabale and live
             * 
             * state is reachable is there is at least one path from start state to that state
             * state is live if there is at least one path from it to an accepting state
             * 
             * in order to get only useful States, all non-reachable and non-live States must be removed, along with
             * their transitions
             * 
             * since there could be whole clusters that are unreachable (none of consisting States is reachable)
             * but live, all unreachable States should be removed first, and then look for States that are not
             * live and remove them too.
             */

            RemoveUnreachableStates();
            RemoveDeadStates();
        }

        public override string ToString()
        {
            //TODO Implementation
            return base.ToString();
        }

        /**
         * Returns <a href="http://www.research.att.com/sw/tools/graphviz/" target="_top">Graphviz Dot</a> 
         * representation of this automaton.
         */
        public string ToDot()
        {
            //TODO Implementation
            return "";
        }
    }
}
